#include <iostream>
using namespace std;

/*
  @brief 定义一个链表结构，
  LNode *L;  声明一个指向单链表第一个节点的指针
  LinkList L;声明一个指向单链表第一个节点的指针（这种可读性更高）
*/
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode, *LinkList;

/// @brief 获取指定位置的链表元素
/// @param L 原始链表
/// @param i 要取元素的位置
/// @return
LNode *GetElem(LinkList L, int i)
{
    int j = 1;
    LNode *p = L->next;
    if (i == 0)
    {
        return L;
    }
    if (i < 1)
    {
        return NULL;
    }
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}

/// @brief 头插法建立单链表
/// @param L
/// @return
LinkList List_HeadInsert(LinkList &L)
{ // 逆向建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode)); // 创建头结点
    L->next = NULL;                      // 初始为空链表
    scanf("%d", &x);                     // 输入节点的值
    while (x != 9999)
    {                                       // 输入“9999” 结束
        s = (LNode *)malloc(sizeof(LNode)); // 创建新节点
        s->data = x;
        L->next = s; // 将新节点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}

/// @brief 初始化一个空的单链表（不带头结点）
/// @param L
/// @return
bool InitListNoHead(LinkList &L)
{
    L = NULL; // 空表，暂时没有节点
    return true;
}

/// @brief 初始化一个单链表（带头节点）
/// @param L
/// @return
bool InitListWithHead(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL)
    {
        return false;
    }
    L->next = NULL;
    return true;
}

/// @brief 判断单链表是否为空（带头节点）
/// @param L
/// @return
bool Empty(LinkList L)
{
    if (L->next == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/// @brief 按位序插入（带头节点）：在第i个位置插入元素e（带头节点）
/// @param L 要插入元素的数组
/// @param i 要插入的位置
/// @param e 要插入的元素
/// @return
bool ListInsertByOrder(LinkList &L, int i, int e)
{
    if (i < 1)
    {
        return false;
    }
    LNode *p;                      // 指针p指向当前扫描到的节点
    int j = 0;                     // 当前指针指向的是第几个节点
    p = L;                         // L指向头结点，头结点是第0个节点（不存数据）
    while (p != NULL && j < i - 1) // 循环找到第i-1个节点
    {
        p = p->next;
        j++;
    }
    if (p == NULL) // i值不合法
    {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s; // 将节点s链接到p之后
    return true; // 插入成功
}

/// @brief 按位序插入（不带头节点）：在第i个位置插入元素e（不带头节点）
/// @param L 要插入元素的数组
/// @param i 要插入的位置
/// @param e 要插入的元素
/// @return
bool ListInsertWithHead(LinkList &L, int i, int e)
{
    if (i < 1)
    {
        return false;
    }
    if (i == 1)
    { // 插入第1个节点的操作与其他节点操作不同
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s; // 头指针指向新节点
        return true;
    }
    LNode *p;  // 指针p指向当前扫描到的节点
    int j = 1; // 当前p指向的是第几个节点
    p = L;     // p指向第1个节点（注意：不是头结点）
    while (p != NULL && j < i - 1)
    { // 循环找到第i-1个节点
        p = p->next;
        j++;
    }
    if (p == NULL)
    { // i值不合法
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true; // 插入成功
}

/// @brief 指定节点的后插操作：在p节点之后插入元素e
/// @param p 指定的节点
/// @param e 要插入的元素
/// @return
bool InsertNextNode(LNode *p, int e)
{
    if (p == NULL)
    {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
    { // 内存分配失败
        return false;
    }
    s->data = e; // 用节点s保存数据元素e
    s->next = p->next;
    p->next = s; // 将节点s连接到p之后
    return true;
}

/// @brief 利用 “指定节点后插操作方法” 在指定位置插入元素
/// @param L
/// @param i
/// @param e
/// @return
bool ListInsertWithHead2(LinkList &L, int i, int e)
{
    if (i < 1)
    { // 插入位置不合法
        return false;
    }
    LNode *p;  // 指针p指向当前扫描的节点
    int j = 0; // 当前p指向的是第几个节点
    p = L;     // L指向头结点，头结点是第0个节点（不存数据）
    while (p != NULL && j < i - 1)
    { // 循环找到第i-1个节点
        p = p->next;
        j++;
    }
    return InsertNextNode(p, e); // 利用指定节点后插操作
}

/// @brief 指定节点的前插操作：在p节点之前插入元素e
/// @param p
/// @param e
/// @return
bool InsertPriorNode(LNode *p, int e)
{
    if (p == NULL)
    {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
    { // 内存分配失败
        return false;
    }
    s->next = p->next;
    p->next = s;       // 将新节点s连到p之后
    s->data = p->data; // 将p中元素复制到s中
    p->data = e;       // p中元素覆盖为e
    return true;
}

/// @brief 按位序删除（带头节点）
/// @param L
/// @param i
/// @param e
/// @return
bool ListDeleteWithHead(LinkList &L, int i, int &e)
{
    if (i < 1)
    {
        return false;
    }
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        return false;
    }
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return e;
}

/// @brief 删除指定节点p
/// @param p
/// @return
bool DeleteNode(LNode *p)
{
    if (p == NULL)
    {
        return false;
    }
    LNode *q = p->next;      // 令q指向*p的后继结点
    p->data = p->next->data; // 节点p和后继结点交换数据域
    p->next = q->next;       // 将*q节点从链中“断开”
    free(q);                 // 释放后继结点的存储空间
    return true; 
}

/// @brief 按位查找，返回第i个元素（带头节点）
/// @param L
/// @param i
/// @return
LNode *GetElemWithHead(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    return p;
}

/// @brief 按值查找，找到  数据域==e  的节点（带头节点）
/// @param L
/// @param e
/// @return
LNode *LocateElem(LinkList L, int e)
{
    LNode *p = L->next;
    // 从第一个节点开始查找数据域为e的元素
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}

/// @brief 求表的长度（带头节点）
/// @param L
/// @return
int Length(LinkList L)
{
    int len = 0; // 统计表长
    LNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

/// @brief 初始化一个单链表（带头节点）
/// @param L
/// @return
bool InitList(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL)
    { // 内存分配失败
        return false;
    }
    L->next = NULL; // 头结点之后暂时还没有节点
    return true;
}

/// @brief 尾插法建立单链表
/// @param L
/// @return
LinkList List_TailInsert(LinkList &L)
{                                        // 正向建立单链表
    int x;                               // 设ElemType为整型
    L = (LinkList)malloc(sizeof(LNode)); // 建立头结点
    LNode *s, *r = L;                    // r为表尾指针
    scanf("%d", &x);                     // 输入节点的值
    while (x != 9999)                    // 输入9999表示结束
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s; // 在r节点后插入元素x
        r = s;       // r指向新的表尾节点（永远保持r指向最后一个节点）
        scanf("%d", &x);
    }
    r->next = NULL; // 尾节点指针为空
    return L;
}

/// @brief 头插法建立单链表（头插法的应用：链表的逆置）
/// @param L
/// @return
LinkList List_HeadInsert(LinkList &L)
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode)); // 创建头结点
    L->next = NULL;                      // 初始为空链表
    scanf("%d", &x);                     // 输入节点的值
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode)); // 创建新节点
        s->data = x;
        s->next = L->next;
        L->next = s; // 将新节点s 头插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}